namespace lzw {

	/* The dictionary size needs to be a	 */
	/* prime number that is somewhat larger  */
	/* than 2**BITS.						 */

	// MAX_BITS == 12
	#define DICTIONARY_SIZE 5021

	//// MAX_BITS == 11
	//#define DICTIONARY_SIZE 2053

	//// MAX_BITS == 10
	//#define DICTIONARY_SIZE 1031

	//// MAX_BITS == 9
	//#define DICTIONARY_SIZE 521

	struct dictionary{
		dictionary(){
			for (int i=0; i<DICTIONARY_SIZE; ++i) {
				code_value[i] = -1;
				prefix_code[i] = 0;
				append_character[i] = 0;
			}
		}
		void reset_dictionary(){
			dictionary();
		}

		int code_value[DICTIONARY_SIZE];
		unsigned int prefix_code[DICTIONARY_SIZE];
		unsigned char append_character[DICTIONARY_SIZE];
	};

	class Decompress {
	public:
		Decompress();
		~Decompress(){};

		enum expand_result { reach_maxcode=0, not_reach_maxcode, expand_failed};
		virtual void init_expand(int min_bit=11, int max_bit=11, int max_dic_use_time=5000); // must call this func before use expand()
		virtual unsigned int expand(unsigned char* arg_input_buf, unsigned int arg_input_len, unsigned char* arg_output_buf, unsigned int arg_output_len);
		virtual expand_result expand_stream(unsigned char* arg_input_buf, unsigned int arg_input_len);
		unsigned int readed_len(void) { return _input_index; }
		unsigned int output_len(void) { return _output_index; }

	protected:
		virtual void output_char(unsigned char c);
		virtual const unsigned char input_char();

		virtual unsigned int input_code();
		virtual unsigned char* decode_string(unsigned char *buffer,unsigned int code);
		virtual void init_dictionary() { _dic.reset_dictionary();}
		virtual void reset_bit(int bit_width);
		unsigned char* _input_buf;
		unsigned char* _output_buf;
		unsigned int _input_len;
		unsigned int _input_index;
		unsigned int _output_index;
		unsigned int _output_len;

		unsigned int _input_bit_count;
		unsigned long _input_bit_buffer;
	private:
		bool _get_head;
		dictionary _dic;
		unsigned int _next_code;
		int character;
		unsigned int old_code;

		unsigned int BITS;				// dic code width
		unsigned int HASHING_SHIFT;
		unsigned int MAX_VALUE;	
		unsigned int MAX_CODE;	

		unsigned int MAX_DIC_BIT;
		unsigned int MIN_DIC_BIT;
		unsigned int MAX_DIC_USED_TIMES;
		unsigned int DIC_USED_TIMES_COUNT;
		unsigned int NEED_CHANGE_BIT;
	};
}
